function bucketSort(arr,bucketSize = 5){ //数组 桶的大小
    if(arr.length < 2){ //如果小于2，直接返回
        return arr
    }
    const buckets = createBuckets(arr,bucketSize) //开始分桶
    return sortBucket(buckets) //桶排序是借助其他排序方法来排序
}

function createBuckets(arr,bucketSize){ //用于分桶的函数
    //let minValue = findMinValue(arr)
    //let maxValue = findMaxValue(arr)
    //上面两行代码循环了两次数组，很耗时间，我们可以换成只循环一次，但是多做一次判断的方法
    let minValue = arr[0] //初始化最大值
    let maxValue = arr[0] //初始化最小值
    for(let index = 1; index < arr.length; index++){
        if(arr[index] > maxValue){ //如果循环到的元素比初始最大值还要大
            maxValue = arr[index] //就更新最大值
        }else if(arr[index] < minValue){ //如果循环到到元素比初始最小值还小
            minValue = arr[index] //就更新最小值
        }
        const bucketCount = Math.floor((maxValue - minValue) / bucketSize) + 1 //多一个桶放多出来的余数
        const buckets = [] //创建一个空数组用来存储生成的各种新数组
        for(let index = 0; index < bucketCount; index++){
            buckets[index] = []
        }

        //把具体的值分到对应的桶
        for(let index = 0; index < arr.length; index++){
            buckets[Math.floor((arr[index] - minValue) / bucketCount)].push(arr[index])
        }
        return buckets //桶生成完成之后就返回
    }
}

function sortBucket(buckets){ //对桶进行排序
    let sortedArr = [] //创建一个最终的数组
    for(let index = 0; index < buckets.length; index++){
        if(buckets[index].length){ //桶里面要有值才进行排序，因为并不是每个桶里面都有值
            quickSort3(buckets[index])
            sortedArr = sortedArr.concat(buckets[index])
        }
    }
    return sortedArr //将最终排好的数组返回
}

//桶排序 借助 快排3 代码量小一些
function quickSort3(arr){
    function quickSort(arr,left,right){
        let l = left
        let r = right
        if(l>=r) return //递归出口
        while(l < r){
            while(arr[l] <= arr[r] && l < r){
                l++
            }
            swap(arr,l,r)

            while(arr[l] <= arr[r] && l < r){
                r--
            }
            swap(arr,l,r)
        }
        let middle = r //取中间值
        quickSort(arr,left,middle-1)
        quickSort(arr,middle,right)
    }
    quickSort(arr,0,arr.length-1)
}

function swap(arr,i,j){ //用于交换的函数
    let temp = arr[i]
    arr[i] = arr[j]
    arr[j] = temp
}

function findMaxValue(arr){ //寻找最大值的函数
    let max = arr[0]
    for(let i = 1; i < arr.length; i++){
        if(arr[i] > max){
            max = arr[i]
        }
    }
    return max
}

function findMinValue(arr){ //寻找最小值的函数
    let min = arr[0]
    for(let i = 1; i < arr.length; i++){
        if(arr[i] < min){
            min = arr[i]
        }
    }
    return min
}

let arr = [1,5,2,3,0,4,6,7,9,8]
bucketSort(arr)